/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 最长回文子串
 * 
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class LongestPalindromicSubstring {
    //动态规划法O(n^2)
    // Manacher方法达到 O(n)
    public String longestPalindrome(String s) {
        int n = s.length();
        int longBegin = 0;
        int maxLen = 1;
        
        boolean dp[][] = new boolean[n][n];
        //单个字符是回文
        for(int i=0;i<n;i++){
            dp[i][i] = true;//对角线初始化
        }
        //紧挨着两个相同字符也是回文
        for(int i=0;i<n-1;i++){
            if(s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1] = true;
                longBegin = i;
                maxLen = 2;
            }
        }
        for(int i=n-3;i>=0;i--){
            for(int j=i+2;j<n;j++){
                if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
                    //如果两端字符相同，取决于内部子串的情况
                    dp[i][j] = true;
                    if(j-i+1>maxLen){
                        longBegin = i;
                        maxLen = j-i+1;
                    }
                }
            }
        }
        String result = s.substring(longBegin, longBegin+maxLen);
        return result;
    }
    public static void main(String[] args) {
        LongestPalindromicSubstring palindromicSubstring = new LongestPalindromicSubstring();
        String s = "aaaabaaa";
        String string = palindromicSubstring.longestPalindrome(s);;
        System.out.println(string);
    }
}
